import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution1971BFS {

    public boolean validPath(int n, int[][] edges, int source, int destination) {
        List<Integer>[] nexts = new ArrayList[n];

        for (int i = 0; i < n; i++) {
            nexts[i] = new ArrayList<>();
        }

        for (int[] edge : edges) {
            int a = edge[0];
            int b = edge[1];

            nexts[a].add(b);
            nexts[b].add(a);
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(source);

        boolean[] been = new boolean[n];

        while (!queue.isEmpty()) {

            int cur = queue.poll();
            for (int next : nexts[cur]) {

                if (next == destination) {
                    return true;
                }

                if (!been[next]) {
                    been[next] = true;
                    queue.add(next);
                }
            }
        }

        return false;
    }


    public static void main(String[] args) {

        System.out.println(new Solution1971BFS().validPath(3, new int[][]{{1, 3}, {2, 3}}, 1, 3));
        System.out.println(new Solution1971BFS().validPath(3, new int[][]{{1, 3}, {2, 3}, {3, 1}}, 1, 2));

    }

}
